package middle;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;

public class Solution_147 {

    public ListNode insertionSortList(ListNode head) {
        List<ListNode> list = new ArrayList<>();
        while (head != null) {
            list.add(head);
            head = head.next;
        }
        list.sort(Comparator.comparingInt(e -> e.val));
        ListNode rst = null;
        for (int i = 0; i < list.size(); i++) {
            if (i == 0) {
                rst = list.get(0);
            } else {
                list.get(i - 1).next = list.get(i);
            }
            list.get(i).next = null;
        }
        return rst;
    }

    class ListNode {
      int val;
      ListNode next;
      ListNode() {}
      ListNode(int val) { this.val = val; }
      ListNode(int val, ListNode next) { this.val = val; this.next = next; }
  }
}
